package recursion;

/**
 * 杨辉三角
 *
 * @author yyz
 * @create 2023-11-15 15:35
 */
public class 杨辉三角 {
    /**
     * 计算杨辉三角中某行某列的值
     *
     * @param i 行
     * @param j 列
     * @return 值
     */
    private static int element(int i, int j) {
        if (j == 0 || j == i) return 1;
        return element(i - 1, j - 1) + element(i - 1, j);
    }

    /**
     * 打印空格
     */
    private static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    /**
     * 打印高度为n的杨辉三角
     *
     * @param n 高度
     */
    private static void print(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element(i, j));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        print3(5);
    }

    /**
     * 计算杨辉三角中某行某列的值（使用记忆法改进）
     *
     * @param i 行
     * @param j 列
     * @return 值
     */
    private static int element2(int i, int j, int[][] memorandum) {

        if (memorandum[i][j] > 0) return memorandum[i][j];

        if (j == 0 || i == j) {
            memorandum[i][j] = 1;
            return memorandum[i][j];
        }
        memorandum[i][j] = element2(i - 1, j - 1, memorandum) + element2(i - 1, j, memorandum);
        return memorandum[i][j];
    }

    /**
     * 打印高度为n的杨辉三角（增加一个二维数组）
     *
     * @param n 高度
     */
    private static void print2(int n) {
        int[][] memorandum = new int[n][];
        for (int i = 0; i < n; i++) {
            memorandum[i] = new int[i + 1];
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element2(i, j, memorandum));
            }
            System.out.println();
        }
    }

    private static void creatRow(int i, int[] row) {
        if (i == 0) {
            row[0] = 1;
            return;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j - 1] + row[j];
        }
    }

    private static void print3(int n) {
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            creatRow(i, row);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);
            }
            System.out.println();
        }
    }
}
